package com.yangzhe.algorithm.c034;

// 复制带随机指针的链表
// 测试链接 : https://leetcode.cn/problems/copy-list-with-random-pointer/
public class Code03_CopyListWithRandomPointer_LeetCode {

    // 不要提交这个类
    public static class Node {
        public int val;
        public Node next;
        public Node random;

        public Node(int v) {
            val = v;
        }
    }

    /**
     * 如下方法不使用额外的容器，额外空间复杂度 O(1)
     * <p>
     * 如果要使用额外的容器，可以使用HashMap记录所有创建的节点即可
     *
     * @param head 头节点
     * @return 复制后的头节点
     */
    public static Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        // 1. 将原链表的复制节点都插入到原节点的下一个节点，例如1复制节点是1'，则
        // 1 -> 2 -> 3 修改为
        // 1 -> 1' > 2 > 2' -> 3 -> 3'
        Node current = head;
        while (current != null) {
            // 保存 2
            Node originNext = current.next;
            // 复制当前节点1 为 1'
            Node copyNode = new Node(current.val);

            // 将 1 连接到 1'：1 -> 1'
            current.next = copyNode;
            // 将 1' 连接到 2：1 -> 1' -> 2
            copyNode.next = originNext;

            current = originNext;
        }

        // 2. 将原节点的随机指针复制到复制节点，复制节点的随机指针就指向原节点随机指针的next节点
        current = head;
        while (current != null) {
            // 例如1 --random--> 3，则 1' --random--> 3.next
            if (current.random != null) {
                current.next.random = current.random.next;
            }

            current = current.next.next;
        }

        // 3. 将复制链表脱离原链表、还原原链表
        current = head;
        Node resultHead = current.next;
        Node resultCurrent = resultHead;
        while (current != null) {
            // 将 1 -> 1' -> 2 - 2' 改为 1 -> 2 -> 2'
            current.next = resultCurrent.next;
            // 将 1' > 2 > 2' 改为 1' > 2'
            if (resultCurrent.next != null) {
                resultCurrent.next = resultCurrent.next.next;
            }

            current = current.next;
            resultCurrent = resultCurrent.next;
        }

        return resultHead;
    }

}
